// https://leetcode.cn/problems/binary-tree-maximum-path-sum/submissions/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = INT_MIN;
    // 该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
    int maxGain(TreeNode* root) {
        if (!root) return 0;
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int left = max(maxGain(root->left), 0);
        int right = max(maxGain(root->right), 0);
        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int newRes = root->val + left + right; 
        res = max(res, newRes);
        return root->val + max(left, right);       
    }
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return res;
    }
};



// https://www.lintcode.com/problem/binary-tree-maximum-path-sum/my-submissions

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

// class Solution {
// public:
    
    // 利用分治法 解决问题
    // 法一：需要一个变量不断记录带有root点的路径的最大值 curr_max 局部变量
    // 需要另一个变量记录当前的最大路径值 max 类变量
    // 最后返回 当前的最大路径值

    // 思路：
    // 有4种情况要考虑
    // left + root
    // right + root
    // root
    // left + right + root
    // 不断往上传递的值 只可能是 1， 2， 3中的一种
    // 第四种情况只可能保存在 max里面 而不可能在 curr_max
    // (curr_max是上传到上一级用的 在上一级 可以用左边的和右边的路径再组合 但是第四种情况是已经穿过root的路径 到上一级就用不了了 不可能跟上一级的root在一起组成新的路径了 所以用于更新max以后就不能用了)
    
    // int max_val = INT_MIN;
    // int help(TreeNode * root)
    // {
    //     if (!root) return 0;
    //     int l = help(root->left);
    //     int r = help(root->right);
    //     int tmp = max(l, r);
    //     if (tmp > 0) tmp = tmp + root->val;
    //     // return max(tmp, l + r) + root->val;
    //     else tmp = root->val;
    //     max_val = max(max_val, max(tmp, l + r + root->val));
    //     return tmp;
    // }
    // int maxPathSum(TreeNode * root) {
    //     help(root);
    //     return max_val;
    // }
    
    // 法二：同时记录singlepath和全局maxpath
struct ResultType {
    int singlePath;
    int maxPath;
};
class Solution {
public:
    ResultType helper(TreeNode * root)
    {
        ResultType re {0, INT_MIN}; //注意初始化
        if (!root) return re;
        ResultType l = helper(root->left);
        ResultType r = helper(root->right);
        re.singlePath = max(max(l.singlePath, r.singlePath), 0) + root->val;
        re.maxPath = max(max(l.maxPath, r.maxPath), l.singlePath + r.singlePath + root->val);
        re.maxPath = max(re.maxPath, re.singlePath);
        return re;
    }
    int maxPathSum(TreeNode * root) {
        ResultType re = helper(root);
        return re.maxPath;
    }
};